﻿namespace Leetcode.N0188;
public class Solution
{
    public int MaxProfit(int k, int[] prices)
    {
        if (k == 0)
        {
            return 0;
        }

        var buy = new int[k];
        var sell = new int[k];

        for (int i = 0; i < prices.Length; i++)
        {
            for (int j = 0; j < k; j++)
            {
                if (i == 0)
                {
                    buy[j] = -prices[i];
                }
                else if (j == 0)
                {
                    buy[j] = Math.Max(buy[j], -prices[i]);
                }
                else
                {
                    buy[j] = Math.Max(buy[j], sell[j - 1] - prices[i]);
                }
                sell[j] = Math.Max(sell[j], buy[j] + prices[i]);
            }
        }
        return sell[k - 1];
    }
}
